1. Technical Field
The invention relates generally to graphs for logic networks and, more specifically, to delay model abstractions created from detailed delay models of logic networks for use with static timing analysis.
2. Background Art
A graph or "model" is a way of representing a network using nodes and edges. In hierarchical designs, abstract models are constructed to express the characteristics of components which are of interest at the higher levels of the design hierarchy in which these components are used, while hiding those characteristics which are not of interest. Thus, an abstract model is a graph that eliminates or reduces the level of detail yet maintains the model characteristics.
One notable analysis for hierarchical designs which uses abstract modeling is static timing analysis. Static timing analysis is used to determine whether a logic circuit meets a set of timing requirements by computing and propagating the worst (latest or earliest) arrival times and possibly required times through the logic network. Unlike logic simulation, no logic values are propagated. Thus the arrival and required times computed are the worst for any possible logic states, allowing a guarantee of timing correctness without having to examine an exponentially large number of cases.
The model used by static timing analysis is a directed delay graph, in which nodes represent points in the logic network at which arrival and required times are computed, propagation edges represent the delay between the points represented by two nodes, and test edges represent a timing requirement (e.g., a setup time) between the points represented by its endpoints. Excluding the test edges, the delay graph is acyclic.
A test edge determines a required time which is a least upper bound on the arrival time at one of its endpoints. At the other endpoint it determines a required time which is a greatest lower bound on the arrival time. Both types of required time are propagated backward through the propagate edges feeding the ends of the test point. In late mode timing analysis, "normal" required times (i.e., those propagated back from primary outputs, or "POs") are least upper bounds on arrival times, while in early mode timing analysis normal required times are greatest lower bounds on arrival times. One conventional method used for labeling test edges consists of calling the end of the test edge at which the required time the test contributes to is of the same type as the normal required times the data end of the test edge, and the other end the clock end of the test edge. The test edges then will be directed from the end imposing a least upper bound required time to that imposing a greatest lower bound required time. The "delay" value on the test edge is how much earlier the signal must arrive at the source end of the test than at the sink end. Although test edges are discussed as one method for indicating timing requirements, other methods, which are also commonly used by one of ordinary skill in the art, could be applied in graphing logical circuits.
To test against a least upper bound required time one should use a maximum arrival time (normal for late mode analysis), while to test against a greatest lower bound required time one should use a minimum arrival time (normal for early mode analysis).
Previous timing analyzers, such as the Early Timing Estimator (ETE), compare both types of required times against the normal type of arrival time for the analysis mode. Thus, the abstraction model does not generate both maximum and minimum delays. This is not normally a problem, since the path along which the arrival time which is not normal for the analysis mode should be propagated is generally a clock path, and these paths usually do not have converging signals, making the maximum and minimum arrival times (for a given set of delays) the same.
However, several problems do occur when the maximum and minimum arrival times are not the same and are not correctly produced in a delay abstraction. Foremost, one cannot know whether the outputs of the logic network being abstracted will feed clock or data pins of tests at the higher levels of the design in which the network is used as a component. Hence, the maximum and minimum arrival times may be different, and both would be necessary for a test edge to accurately determine required times of both the greatest lower bound and least upper bound of arrival times.
The article "Hierarchical Delay Predictor and Corrector," IBM Technical Disclosure Bulletin, No. 2, July 1990, pp.81-83; describes methods for generating abstract delay models for hierarchical designs. Only primary input (PI) and primary output (PO) nodes are used in the abstract delay graph generated by this method. Unfortunately, generating a abstract delay graph can require far more delay graph edges than needed, thus requiring more storage space. For example, if the initial delay graph were to have NPIs, each of which with an edge to a single internal node X; and M outputs, each with an edge form X; the original delay model would only have N +M edges, while the abstract delay model would have N * M edges.
Other examples of modeling hierarchical designs may be found in the following United States Patents, each incorporated herein by reference: U.S. Pat. No. 4,924,430, "Static Timing Analysis of Semiconductor Digital Circuits," (issued May 1990 to Zasio et al and assigned to Teradyne, Inc); U.S. Pat. No. 5,047,969, "General Network Modeling and Synthesis," (issued Sep. 1991 to Sloane and assigned to Schlumberger Technologies, Ltd); U.S. Pat. No. 5,163,016, "Analytical Development and Verification of Control-Intensive Systems," (issued November 1992 to Har'El et al and assigned to AT&T Bell Laboratories); U.S. Pat. No. 5,251,147, "Minimizing the Interconnection Cost of Electronically Linked Objects," (issued October 1993 to Finnerty and assigned to Digital Equipment Corp.); U.S. Pat. No. 5,253,161, "Method for Routing Data in a Near-Optimal Manner in a Distributed Data Communications Network," (issued October 1993 to Nemirovsky et al); and U.S. Pat. No. 5,262,959, "Representation and Processing of Hierarchical Block Designs," (issued Nov. 1993 to Chkoreff and assigned to Hewlett-Packard Co.).
Although each aforementioned patent provides a unique way to model a hierarchical or similar design, they do not describe using both the maximum and minimum arrival times in generating delay abstraction models. Furthermore, each method for doing static timing analysis on a delay graph share the property that the time required is linear in the number of edges in the delay graph. None of these patents address the problem of reducing the storage associated in using delay graph abstraction.